﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DirectedGraphCycle
{
    class StrongConnectedComponents
    {
        private List<int>[] adjacencyListOriginal = null;
        private List<int>[] adjacencyListCurrent = null;
        private int numNodes = 0;

        //Use for Tarjan SCC algorithm
        private bool[] visited = null;
        private int[] lowlink = null;
        private int[] index = null;
        private Stack stack = null;
        private int time = 0;

        //Contain all SCC of subgraph which has all nodes >= node
        private ArrayList listCurrentSCC = null;

        public StrongConnectedComponents(List<int>[] adjacencyListOriginal)
        {
            this.adjacencyListOriginal = adjacencyListOriginal;
            numNodes = this.adjacencyListOriginal.Length;
        }

        public SCCResult getStrongConnectedComponent(int node)
        {
            this.listCurrentSCC = new ArrayList();
            this.initSubGraph(node);

            for (int i = node; i < numNodes; i++)
            {
                this.strongconnect(i);
                ArrayList nodes = this.getLowestIdSCC();
                if (nodes != null && !nodes.Contains(node))
                {
                    return this.getStrongConnectedComponent(node + 1);
                }
                else if (nodes != null && nodes.Contains(node))
                {
                    ArrayList[] adjacencyList = this.getSCCSubGraph(nodes);
                    if (adjacencyList != null)
                    {
                        for (int j = 0; j < numNodes; j++)
                        {
                            if (adjacencyList[j].Count > 0)
                            {
                                return new SCCResult(adjacencyList, j);
                            }
                        }
                    }
                }

            }

            return null;
        }

        //Make sub graph contains only edge between two vetexes larger than node
        public void initSubGraph(int node)
        {
            this.visited = new bool[numNodes];
            this.lowlink = new int[numNodes];
            this.index = new int[numNodes];
            this.stack = new Stack();
            this.time = 0;

            this.adjacencyListCurrent = new List<int>[numNodes];
            for (int i = 0; i < node; i++)
            {
                this.adjacencyListCurrent[i] = new List<int>();
            }

            for (int i = node; i < numNodes; i++)
            {
                this.adjacencyListCurrent[i] = this.adjacencyListOriginal[i].Where(element => element >= node).ToList<int>();
            }
        }

        //Get sub graph of SCC contains only edge between two vertexes in nodes
        public ArrayList[] getSCCSubGraph(ArrayList nodes)
        {
            ArrayList[] subGraph = null;
            if (nodes != null)
            {
                subGraph = new ArrayList[numNodes];
                for (int i = 0; i < subGraph.Length; i++)
                {
                    subGraph[i] = new ArrayList();
                }
                for (int i = 0; i < nodes.Count; i++)
                {
                    int v = (int)nodes[i];
                    for (int j = 0; j < this.adjacencyListCurrent[v].Count; j++)
                    {
                        int w = this.adjacencyListCurrent[v][j];
                        if (nodes.Contains(w))
                        {
                            subGraph[v].Add(w);
                        }
                    }
                }
            }
            return subGraph;
        }

        //Get the SCC has lowest node is lowest
        public ArrayList getLowestIdSCC()
        {
            int min = numNodes;
            ArrayList currScc = null;

            for (int i = 0; i < this.listCurrentSCC.Count; i++)
            {
                ArrayList scc = (ArrayList)this.listCurrentSCC[i];
                for (int j = 0; j < scc.Count; j++)
                {
                    if ((int)scc[i] < min)
                    {
                        currScc = scc;
                        min = (int)scc[i];
                    }
                }
            }
            return currScc;
        }

        //Tarjan SCC algorithm
        private void strongconnect(int v)
        {
            this.index[v] = this.time;
            this.visited[v] = true;
            this.lowlink[v] = this.time;
            this.time++;
            this.stack.Push(v);

            for (int i = 0; i < this.adjacencyListCurrent[v].Count; i++)
            {
                int w = this.adjacencyListCurrent[v][i];
                if (!this.visited[w])
                {
                    this.strongconnect(w);
                    this.lowlink[v] = Math.Min(lowlink[v], lowlink[w]);
                }
                else if (this.stack.Contains(w))
                {
                    lowlink[v] = Math.Min(this.lowlink[v], this.index[w]);
                }
            }

            if (lowlink[v] == index[v])
            {
                int node = -1;
                ArrayList scc = new ArrayList();
                do
                {
                    node = (int)stack.Pop();
                    scc.Add(node);
                } while (v != node);

                if (scc.Count > 1)
                {
                    this.listCurrentSCC.Add(scc);
                }
            }
        }

    }

    public class SCCResult
    {
        private HashSet<int> nodeIDsOfSCC = null;
        private ArrayList[] adjList = null;
        private int lowestNodeId = -1;

        public SCCResult(ArrayList[] adjList, int lowestNodeId)
        {
            this.adjList = adjList;
            this.lowestNodeId = lowestNodeId;
            this.nodeIDsOfSCC = new HashSet<int>();
            if (this.adjList != null)
            {
                for (int i = this.lowestNodeId; i < this.adjList.Length; i++)
                {
                    if (this.adjList[i].Count > 0)
                    {
                        this.nodeIDsOfSCC.Add(i);
                    }
                }
            }
        }

        public ArrayList[] getAdjList()
        {
            return adjList;
        }

        public int getLowestNodeId()
        {
            return lowestNodeId;
        }
    }

}
